\documentclass[a4paper,11pt]{article}
\usepackage{fancyhdr}
\setlength{\headheight}{11pt}
\pagestyle{fancyplain}
%\renewcommand{\chaptermark}[1]{\markboth{#1}{}}

\lhead{ }
\rhead{}
%\renewcommand{\headrulewidth}{0.0pt}

\lfoot{Group 23: Planning proposal}
%COMMENT: Y is the topic which has been assigned to you
\cfoot{\thepage}
\rfoot{}

%
%%    homebrew commands -- to save typing
\newcommand\etc{\textsl{etc}}
\newcommand\eg{\textsl{eg.}\ }
\newcommand\etal{\textsl{et al.}}
\newcommand\Quote[1]{\lq\textsl{#1}\rq}
\newcommand\fr[2]{{\textstyle\frac{#1}{#2}}}
\newcommand\miktex{\textsl{MikTeX}}
\newcommand\comp{\textsl{The Companion}}
\newcommand\nss{\textsl{Not so Short}}

%% #  It is forbidden to remove sections, or to change their placement
%% #  inside the template. You are allowed to add sub-sections or one
%% #  appendix.

%% # Observe SIZE limits:
%%     * proposal must not exceed 8 pages. 

%% # Observe minimum REFERENCES required:
%%     * proposal must reference and use at least two published papers. 

%% # Observe minimum CONTENTS expected:

%%     * each pre-proposal must include some algorithms for key parts
%%       of the problem at an abstract level. This ensures a concrete
%%       understanding.

%%     * the proposal must extend the pre-proposal algorithms set with
%%       other problem-related procedures.

\begin{document}
%-----------------------------------------------------------
\title{
Solving Rubik's Cube \\
with a Planner}
\author{Group 23: Disa Faith, Ted Lilljegren, Per P{\aa}lsson, G\"{o}ran Weinholt}
\maketitle
%-----------------------------------------------------------
\begin{abstract}%\centering
%%COMMENT
%% no more than 10 lines!

Rubik's Cube is a popular puzzle that has been the focus of much
research. It was recently shown that every instance of the puzzle can
be solved in twenty steps and much of the literature talks about
finding optimal solutions. We propose a project to develop software
inspired by the ideas behind these searches for optimal solutions. The
direction of our work will be towards implementing an algorithm that
does not necessarily find optimal solutions, but that is simpler than
the published algorithms.

\end{abstract}

\section{Introduction}
\subsection{What is the problem you are trying to solve?}
%% Define the problem

Rubik's Cube is a three dimensional puzzle created by Ern\H{o} Rubik
in 1974. There are several variants, but we will be working with the
original model. The cube is divided into $3^3$ smaller \emph{cubies}
and the six faces of the cube are each composed of nine colored
\emph{facelets}. The middle of the cube is part of a mechanism that
lets a person rotate the sides of the cubes. The cube is \emph{solved}
when the facelets on all faces have identical colors.

We will develop a planning agent that attempts to solve a scrambled
cube. Because an exhaustive search is not feasible we will need to use
more effective algorithms with some expert input.

\subsection{What results are available in the literature on that problem?}
\label{sec:results}
%%(describe briefly the scientific papers you found relevant to the
%%problem, references to sec 4.)

%% Give background and explanations with references to the literature
%% describing previous attempts to solve, analyse or elucidate the
%% problem

%% Outline:
%% Folk har letat efter en upper bound
%% Givet detta, varför inte göra en enkel sökning?
%% Det tar för mycket minne
%% En något mer invecklad sökning krävs, IDA*
%% A* behöver heuristik, presentera de vi hittat
%% Kociembas kan ses som IDA* med mindre sökrymd
%% Andra sätt att angripa problemet - evolutionary-grejerna
%% Men vi gör AP, inte ML, därför är Kociemba-stuket bättre

Much of the literature focuses on the theoretical aspect of the
minimum number of steps required to solve an arbitrarily scrambled
cube. Michael Reid proved in 1995 a lower bound of 20
moves\cite{cube20}. At that time the proven upper bound was 29 moves.
The lower and upper bounds have been getting closer for 30 years.

Rokicki proved in 2008 that there is no cube that needs more than 25
moves\cite{rok1}. His work extended Kociemba's \emph{two-phase
  algorithm}\cite{koc1} to make it find shorter solutions and to do so
faster than before. Last year an upper bound of 20 moves was
proven\cite{cube20} by a massive exhaustive search, which means that
the problem is now closed.

In light of this proven upper bound, one might wonder if some sort of
uninformed search couldn't be used to solve the problem. Russell and
Norvig\cite{norvig1} describe the method of bidirectional search,
which seems most promising. The upper bound of $d=20$ applies to
\emph{face turns} and there are $b=6(3)$ different face turns. A
breadth-first search would visit $O(b^{d})$ nodes, but the
bidirectional search only visits $O(b^{d/2})$ nodes.

The bidirectional search would be implemented by creating a hashtable
of all possible face turn sequences of length $10$. To solve a
scrambled cube one would again perform all such sequences of length
$10$, but starting at the scrambled cube instead. Additionally one
would look up the resultant cubes in the previously created hashtable.
If a match is found then one simply combines the current list of moves
with the moves that were used to generate the entry in the hashtable.

This approach requires a lot of memory to store the hashtable. We can
roughly estimate the memory requirement by counting the number of
entries in the hashtable. We have $18$ possible face moves and we need
to store all sequences of length $10$, which gives us $18^{10}\approx
3.6\times 10^{12}$ entries. If we very generously approximate the size
of each entry as one byte, this still means we need slightly more than
$3$ terabytes of memory. The table size can be decreased by using the
fact that after one face turn, there are some face turns that are
illegal, because they could have been reached with just one face turn.
Even with this optimization the table has a substantial size. The
personal computers of today have around a thousand times less memory
than that required by the table, so this approach is currently only
feasible with supercomputers.

This brings us to informed search. To use A* search we need an
admissible heuristic for the cube. There is no obvious heuristic we
can use. Simpler heuristics, e.g.~just counting the number of
misplaced facelets, severly overestimate the solution distance. But
there are some useful heuristics, e.g.~the \emph{Center-Corner}
heuristic, that was found by Prieditis' {\sc Absolver} program. By
using this heuristic with iterative-deepening A* search (IDA*), his
program ran eight orders of magnitude faster than a breadth-first
search\cite{prie}. Another kind of heuristic for the Rubik's Cube is a
\emph{pattern database}. Korf developed this heuristic in order to
find optimal solutions with IDA* and it is based on in-memory tables
of solutions for all possible combinations of corner
cubies\cite{korf97}.

Kociemba's two-phase algorithm also uses heuristics. Instead of
directly attacking the whole state-space of the cube, the two-phase
algorithm divides the problem into two subproblems. The basis of the
algorithm is that if you restrict your movements on the cube to a
certain small subset of all possible moves, you can only reach a small
subgroup of all possible states. It is feasible to use IDA* to find a
set of moves that puts a scrambled cube into this subgroup, and then
it is feasible to search from the subgroup to the completely solved
cube. The algorithm is based on an earlier algorithm by
Thistlethwaite, which used more subgroups\cite{koc1}.

Recent research on the cube has used evolutionary
algorithms\cite{nail1}\cite{nail2}. This work builds on the subgroups
of Thistlethwaite's algorithm, and another approach based on
pre-defined move sequences that perform some specific functions. This
research would be very interesting if our project was in Machine
Learning, but since we are in Automated Planning we will instead try
to use the work described in the earlier paragraphs.

\subsection{What tools and programs are already available for the problem, or for closely related ones?}
\label{sec:tools}
%%(describe these briefly. Say how you can use them, and how your work
%%will build on them, or differ from them).

Kociemba has implemented his two-phase algorithm as a program for
Microsoft Windows\cite{koc1}. Kociemba's program tries to find optimal
solutions, which is not our goal. For GNU/Linux systems there is
Gnubik\cite{gnubik}, which includes a solver that does not attempt to
find optimal solutions.

Many methods for solving the cube are ``human'' methods, i.e.~they are
instructions that humans can use to solve the cube in a couple of
stages. Contests are held where the participants attempt to solve the
cube in the fastest time, and one popular method for this has been
developed by Lars Petrus\cite{petrus}. These methods can also be
implemented in software.

We will probably not have much use for the ``human'' methods, because
they are more akin to manual planning than automated planning.
Kociemba's program might be useful as a benchmark and we will also be
using ideas from his research. The algorithm used in Gnubik is a lot
like the manual methods and does not seem too interesting, except
perhaps as a benchmark for how good the manual solutions can be.

\section{Key ideas and delimitations}

\subsection{Why is the problem interesting or significant?  What will a solution achieve?}
%% Say why you picked the problem, and your goals for your work with it

Solving Rubik's Cube with computers is nothing new. But instead of
using a specialized algorithm like Kociemba's two-phase algorithm,
where all the intelligence was in the creation of the algorithm, it
would be interesting to solve the cube with a simpler algorithm.

\subsection{The central idea in your solution}
%% Outline how you would attack the problem

We will not give priority to finding optimal solutions, like so much
of the research has been focused on. Most problems are best solved by
splitting the problem into smaller subproblems and our reading of the
literature suggests that it is infeasible to attempt a solution that
is not based on subgroups. It is our belief that we can develop a
solver based on Kociemba's subgroups, but instead using algorithms
that sacrifice efficiency for simplicity.

Our first step will be to generate a table of the cubes that can be
reached with ten moves from Kociemba's subset of moves, i.e.~generate
Kociemba's subgroup. The second step is to take a scrambled cube and
search for a sequence that puts it in the subgroup.

\subsubsection{Why do you think it will work?}

As previously mentioned, Kociemba's two-phase algorithm goes to some
extra effort to find optimal solutions quickly. If the math that was
used to develop Kociemba's algorithm is accurate, then we can create a
simpler manifestation of that math with our program.

Since we will try to use bidirectional search, we have to be careful
that our table size does not grow too large. To limit the lookup table
the legal operations on the cube have to be limited to prevent several
operations that provide the same outcome. For instance, consecutive
moves on the same face do not yield any other result than one single
move does. With the defined set of moves, we have 6 faces with 3 valid
moves on each face, and after the first move has been performed 3
moves will be illegal in the next turn. This will give us a smaller
set for the database since we limit the useless moves. The previous
$18^{10}$ moves for a database with distance 10 would then be reduced
to $18(15^9)$ moves. To further limit the lookup table, the order of
which side the move is applied on matters as well. For instance, when
moves are applied to opposite sides, the order doesn't matter since
they don't affect the outcome of each other. Using this fact, half of
the faces will have another three operations that are invalid. By
allowing relabeling of the cube, which would mean the cube would be
allowed to be turned, there will also be symmetries that provide us
with yet another decrease of moves contained in the lookup database.

The method used in Kociemba's two-phase algorithm significantly
decreases the size of the search space by limiting it to a pre-defined
subset of moves. The subset allowed for the lookup table has 6 legal
moves which would give a lookup table with $6^{10}$ entries given
this. In comparison this would decrease the amount of moves from the
initial $18^{10}$ which is about $3.6(10^{12})$ to about $60(10^6)$.
These techniques work, but we will try to use as few of these clever
optimizations as we can get away with.

\subsection{Define an instance of the problem. How will you measure the performance of your program?}
%%(You must know this in advance, find instances /benchmarks, or make your own).

If one simply assigned the colors of the facelets randomly, one would
likely end up with an illegal permutation that could not be solved. We
therefore define a problem instance as a scrambled cube, i.e.~a solved
cube that has been permuted by a sequence of legal moves. It should be
enough to generate 100 random moves\cite{korf97}.

One approach to testing the program is to provide it with a set of
scrambled cubes and see if they are all solvable by the program. The
performance can then be measured by comparing the lengths of its
solutions with the proven upper bound of 20. We believe that this will
be very unfavorable to our program, so an alternative measure will
compare the solutions with those produced by Gnubik\cite{gnubik}.
Although Gnubik uses an algorithm designed specifically for the cube,
its solutions are on the order of two hundred moves. We will actually
be happy if our program can solve any cubes at all.

Another important part of our performance measure is the algorithm
running time. The fact that the problem is closed means that we could
simply write a search algorithm that looks at all move sequences of
length 20. This would eventually find a solution, but it would take so
much time that it would be impractical. Cube Explorer and Gnubik solve
the cube in a few seconds. To be practical our program should not take
more than a few minutes to find solutions.

\subsection{The scope of your work}

%%(also, what interesting and related things are outside the scope of your proposal?)

The goal is to create a planning agent that solves Rubik's Cube using
a simple algorithm and with a simple graphical interface. The focus
will not be on finding the most efficient, optimal solutions. It might
be interesting to compare the algorithmic complexity of our solver
with other available solvers, but we will not do this.

\section{First results}

%% Give a small piece of pseudo-code to concretely explain a central
%% part of the problem and a (perhaps naive) solution to this part

%%(A small piece of pseudo-code for a key part of the solution. )

Search for a list of moves that will get the cube into the subgroup G1.

\begin{verbatim}
//List of moves from 0-17 representing U, U1, U2
function search(ScrambledCube) {
  cubeNode = ScrambledCube;
  for (i=0; i<18, i++) {
    cubeNode = transform(cubeNode, move(i));
    compare cubeNode to G1 partial solution;
    if (cubeNode == solvedCube) {
      add move(i) to action list;
      set status solved;
      break loop;
    }
  }
  if (status !solved) {
    for (i=0; i<18, i++) {
      cubeNode = transform(cubeNode, move(i));
      add move(i) to action list;
      cubeNode = search(cubeNode);
      compare cubeNode to G1 partial solution;
      if (cubeNode == solvedCube) {
        set status solved;
        break loop;
      }
    }
  }
}

function compare(cubeNode) { 
  for (i=0; i<hashTable.entryLength; i++) { 
    if (hashTable.entry(i) == cubeNode) { 
      status = solved; 
      break; 
    } 
  } 
  return status; 
} 
\end{verbatim}

Create the table for bidirectional search.

\begin{verbatim}
function generateG1(int depth, cubeNode) {
  //List of moves from G1 {U,D,R2,L2,F2,B2}
  for (i=0; i<6; i++) {
    cubeState = transform(cubeNode, move(i));
    if (depth > 0) {
      depth--;
      generateG1(depth, cubeState);
    } else {
      store(cubeState, hashTable);
    }
  }
}
\end{verbatim}

\renewcommand*{\refname}{}
\section{References}
\begin{thebibliography}{9}

\bibitem{norvig1}
\begin{enumerate}
\item
  Russell, S., Norvig, P. (2010)
  \emph{``Artificial Intelligence: A Modern Approach''},
  Prentice Hall, \textbf{pp.~90}.
\item
  This is the course textbook.
\item
  We reference the textbook in Section~\ref{sec:results}.
\end{enumerate}

\bibitem{rok1}
\begin{enumerate}
\item
  Rokicki, T. (2008).
  \emph{``Twenty-Five Moves Suffice for Rubik's Cube''}.
  arXiv:0803.3435v1,
  http://arxiv.org/abs/0803.3435v1
  (retrieved: 2011-04-17).
\item
  This paper proved a lower bound of 25 moves.
\item
  We reference this paper in Section~\ref{sec:results}.
\end{enumerate}

\bibitem{rok2}
\begin{enumerate}
\item
  Rokicki, T. (2010).
  \emph{``Twenty-Two Moves Suffice for Rubik's Cube\textsuperscript{\textregistered}''}.
  The Mathematical Intelligencer,
  http://dx.doi.org/10.1007/s00283-009-9105-3
\item
  This paper proved a lower bound of 22 moves.
\item
  We reference this paper in Section~\ref{sec:results}.
\end{enumerate}

\bibitem{koc1}
\begin{enumerate}
\item
  Kociemba, H.
  \emph{``Cube Explorer''},
  http://kociemba.org/cube.htm (retrieved: 2011-04-15).
\item
  This is a Windows program that solves the cube with Kociemba's two-phase
  algorithm. The website also provides a detailed description of the
  theory behind the algorithm.
\item
  We reference this website in Section~\ref{sec:tools}.
\end{enumerate}

\bibitem{cube20}
\begin{enumerate}
\item
  Rokicki, T., Kociemba, H., Davidson, M., and Dethridge, J.
  \emph{``God's Number is 20''},
  http://cube20.org/ (retrieved: 2011-04-15).
\item
  The authors have solved all positions of the cube and proven
  an upper bound of 20, thus closing the problem.
\item
  We reference this website in Section~\ref{sec:results}.
\end{enumerate}

\bibitem{gnubik}
\begin{enumerate}
\item
  Darrington, J.~M.
  \emph{``Gnubik''},
  The Free Software Foundation,
  http://www.gnu.org/software/gnubik/ (retrieved: 2011-04-17).
\item
  This is a {\sc gnu} program that can be used to view, manipulate and
  solve cubes.
\item
  We reference this software in Section~\ref{sec:tools}.
\end{enumerate}

\bibitem{prie}
\begin{enumerate}
\item
  Prieditis, A.~E. (1993)
  \emph{``Machine discovery of effective admissible heuristics''},
  Machine Learning, pp. 117--141,
  http://dx.doi.org/10.1007/BF00993063
\item
  The author developed a program that discovered a useful heuristic
  for Rubik's Cube.
\item
  We reference this paper in Section~\ref{sec:results}.
\end{enumerate}

\bibitem{korf97}
\begin{enumerate}
\item
  Korf, R.~E. (1997)
  \emph{``Finding Optimal Solutions to Rubik's Cube Using Pattern Databases''},
  AAII-97 Proceedings,
  https://www.aaai.org/Papers/AAAI/1997/AAAI97-109.pdf
  (retrieved: 2011-04-17).
\item
  The author has used IDA\* together with heuristics called ``pattern
  databases'', that are tables generated by a breadth-first search for
  the number of moves required for a partial solution.
\item
  This paper is referenced in Section~\ref{sec:results}.
\end{enumerate}

%% Excellent journal: http://www.sciencedirect.com/science/journal/00043702
%% \bibitem{bonet}
%% \begin{enumerate}
%% \item
%%   Bonet, B., Geffner, H. (2001)
%%   \emph{``Planning as heuristic search''},
%%   Artificial Intelligence, Volume 129, Issues 1--2, June 2001, Pages 5--33,
%%   http://dx.doi.org/10.1016/S0004-3702(01)00108-4
%% \item
%%   %%
%% \item
%%   %%
%% \end{enumerate}

\bibitem{nail1}
\begin{enumerate}
\item
  El-Sourani, N., Borschbach, M. (2011)
  \emph{``Design and Comparison of two Evolutionary Approaches for Solving the Rubik's Cube''},
  Lecture Notes in Computer Science, Volume 6239/2011, pp. 442--451
  http://dx.doi.org/10.1007/978-3-642-15871-1\_45
\item
  The authors evaluate two evolutionary algorithms for solving the
  cube.
\item
  This paper is referenced in Section~\ref{sec:results}.
\end{enumerate}

\bibitem{nail2}
\begin{enumerate}
\item
  El-Sourani, N., Hauke, S., Borschbach, M. (2010)
  \emph{``An Evolutionary Approach for Solving the Rubik's Cube Incorporating Exact Methods''},
  Lecture Notes in Computer Science, Volume 6024/2010, pp. 80--89
  http://dx.doi.org/10.1007/978-3-642-12239-2\_9
\item
  The authors develop an evolutionary algorithm based on
  Thistlethwaite's algorithm.
\item
  This paper is referenced in Section~\ref{sec:results}.
\end{enumerate}

\bibitem{petrus}
\begin{enumerate}
\item
  Petrus, L.
  \emph{``Solving Rubik's Cube for speed''},
  http://lar5.com/cube/ (retrieved: 2011-04-19).
\item
  The author describes his method for solving the cube by hand.
\item
  This paper is referenced in Section~\ref{sec:tools}.
\end{enumerate}


\end{thebibliography}

%% Reminder: References should be cited (i.e. actually be referred to)
%% at the appropriate place in your text, they should visibly inßuence
%% your document, and they should convey as much information as
%% possible to the reader.

%% For most of you, our previous instructions were not enough to
%% produce a good document. So to help produce a good literature
%% survey, we are now asking for a more elaborate structure, an
%% annotated list of references.

%% A reference to a paper will start with a unique ID (numbers,
%% letters, ...) and have the following three paragraphs:
%% \begin{enumerate}
%% \item Author(s) [year of publication], ``Title of paper'', Journal
%% (or conference etc.), location data (i.e., volume numbers, etc.
%% needed to Þnd the item), a live www link if available.
%% \item A couple of lines saying what question the paper is
%% attacking, and what the proposed solution is. Or what topic the
%% reference deals with (your textbook has excellent examples in the
%% sections entitled ``Bibilographical and Historical notes'').
%% \item A pointer back to where you cite this reference.
%% \end{enumerate}

%% An example would look like this:
%% \newline
%% [REF1]
%% \begin{enumerate}
%% \item Turing, A.M. (1936).`On Computable Numbers, with an
%% Application to the Entscheidungsproblem". Proceedings of the London
%% Mathematical Society. 2 42: 230Ð65.
%% \item The paper is about ...
%% \item The most important reference to this paper in our document is
%% in Section XYZ
%% \end{enumerate}

%% A reference to a specific topic in a book (or large survey article)
%% has similar 2nd. and 3rd. paragraphs, but the first will look like
%% this:

%% \begin{enumerate}
%% \item Author(s) [year of publication], ``Title of book'', Publisher, a live www link if available.
%% \textbf{Section numbers or page numbers in the book dealing with the material you are referring to}.
%% \end{enumerate}

\section{Appendix}
%% The first 3 sections (excluding title page and references) are
%% limited to 8 pages. Here, you can put in anything that didn't fit
%% in there, but that you still think is essential.

Rubik's Cube is a registered trademark of Seven Towns, Ltd.

%% \subsection{Kociemba's Algorithm}
%% The theory behind the algorithm is that from a certain set of defined
%% moves, the cube can be changed into a subset of any available cube
%% there is. If the cube from its scrambled state is returned to this
%% subset, the moves used to generate the subset can be used to restore
%% the cube from this state to its solved state. Part one of the
%% algorithm restores the cube to a subset of the scrambled cube using a
%% search algorithm and part two then restores it to its original state.
%% After a solution is found the program will continue to look for
%% shorter solutions by finding solutions with fewer steps in step two of
%% the algorithm and more in step one. When step two no longer needs any
%% moves the optimal solution should have been found.


\end{document}
